package com.itheima.algorithm.binarytree;

import com.itheima.algorithm.stack.LinkedListStack;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author: TylerZhong
 * @description:
 */
public class E01Leetcode144 {


    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> lists = new ArrayList<>();

        LinkedList<TreeNode> stack = new LinkedList<>();
        TreeNode curr = root; // 代表当前节点
        TreeNode pop = null; // 最近一次弹栈的元素
        while (curr != null || !stack.isEmpty()) {
            if (curr != null) {
                stack.push(curr); // 压入栈，为了记住回来的路
                lists.add(curr.val);
                // 待处理左子树
                curr = curr.left;
            } else {
                TreeNode peek = stack.peek();
                if (peek.right == null) { // 没有右子树
                    pop = stack.pop();
                } else if (peek.right == pop) { // 右子树处理完成
                    pop = stack.pop();
                } else { // 待处理右子树
                    curr = peek.right;
                }
            }
        }
        return lists;
    }
}
